#include "dijkstra.hpp"
#include <string>

using namespace std;


/* Fonctions internes pour tab_dist
    initItemDist()
    agrandirTabDist()
    ajoutItemDist()
 */

/* Structure tab_dist
        struct item_dist {
            Noeud* destination;
            int distance;
        };

        struct tab_dist {
            int nb_items;
            int capa_items;
            item_dist** contenu;
};
 */

item_dist * initItemDist(Noeud* n, int dist) {
    item_dist * id = (item_dist*) malloc(sizeof (item_dist));

    id->destination = n;
    id->distance = dist;

    return id;
}

void agrandirTabDist(tab_dist * tbd) {

    if (tbd->nb_items == tbd->capa_items) {
        if (tbd->capa_items == 0) {
            tbd->capa_items = 1;
            tbd->contenu = (item_dist**) malloc(tbd->capa_items * sizeof (item_dist*));
        } else {
            tbd->capa_items *= 2;
            tbd->contenu = (item_dist**) realloc(tbd->contenu, tbd->capa_items * sizeof (item_dist*));
        }
    }
}

void ajoutItemDist(tab_dist * tbd, item_dist * id) {
    agrandirTabDist(tbd);

    tbd->contenu[tbd->nb_items] = id;
    tbd->nb_items++;
}

int rechercheItemDist(tab_dist* tbd, Noeud* n) {

    for (int i = 0; i < tbd->nb_items; i++) {
        if (tbd->contenu[i]->destination->nom == n->nom) {
            return i;
        }
    }

    return -1;
}

// Fonctions pour tab_dist

tab_dist* initTabDist(bool verbose) {
    tab_dist* tbd = (tab_dist*) malloc(sizeof (tab_dist));

    tbd->capa_items = 0;
    tbd->nb_items = 0;
    tbd->contenu = NULL;

    return tbd;
}

void ajoutElemDist(tab_dist* tbd, Noeud *n, int dist) {
    item_dist * id = initItemDist(n, dist);
    ajoutItemDist(tbd, id);
}

void modifDist(tab_dist* tbd, Noeud *n, int dist) {
    int ind = rechercheItemDist(tbd, n);
    if (ind >= 0)
        tbd->contenu[ind]->distance = dist;
}

int distanceNoeud(tab_dist* tbd, Noeud *n) {
    int ind = rechercheItemDist(tbd, n);

    return tbd->contenu[ind]->distance;
}

void testamentTabDist(tab_dist* tbd) {
    for (int i = 0; i < tbd->nb_items; i++) {
        tbd->contenu[i]->destination = NULL;
        tbd->contenu[i]->distance = 0;
        free(tbd->contenu[i]);
    }
}

/* ====================================================================== */
/*  Fonctions internes pour tab_prev
    initItemPrev()
    agrandirTabPrev()
    ajoutItemPrev()
 */

/* Structures pour tab_prev

            struct item_prev {
                Noeud* actuel;
                Noeud* precedent;
            };

            struct tab_prev {
                int nb_items;
                int capa_items;
                item_prev** contenu;
            };
 */

item_prev * initItemPrev(Noeud* n, Noeud* prev) {
    item_prev * ip = (item_prev*) malloc(sizeof (item_prev));

    ip->actuel = n;
    ip->precedent = prev;

    return ip;
}

void agrandirTabPrev(tab_prev * tbp) {

    if (tbp->nb_items == tbp->capa_items) {
        if (tbp->capa_items == 0) {
            tbp->capa_items = 1;
            tbp->contenu = (item_prev**) malloc(tbp->capa_items * sizeof (item_prev*));
        } else {
            tbp->capa_items *= 2;
            tbp->contenu = (item_prev**) realloc(tbp->contenu, tbp->capa_items * sizeof (item_prev*));
        }
    }
}

void ajoutItemPrev(tab_prev * tbp, item_prev * ip) {
    agrandirTabPrev(tbp);

    tbp->contenu[tbp->nb_items] = ip;
    tbp->nb_items++;
}

int rechercheItemPrev(tab_prev* tbp, Noeud* n) {

    for (int i = 0; i < tbp->nb_items; i++) {
        if (tbp->contenu[i]->actuel->nom == n->nom) {
            return i;
        }
    }

    return -1;
}

// Fonctions pour tab_prev

tab_prev* initTabPrev(bool verbose) {
    tab_prev * tbp = (tab_prev*) malloc(sizeof (tab_prev));

    tbp->capa_items = 0;
    tbp->nb_items = 0;
    tbp->contenu = NULL;

    return tbp;
}

void ajoutElemPrev(tab_prev* tbp, Noeud *actuel, Noeud *prev) {
    item_prev * ip = initItemPrev(actuel, prev);
    ajoutItemPrev(tbp, ip);
}

void setElemPrev(tab_prev* tbp, Noeud *actuel, Noeud *prev) {
    int ind = rechercheItemPrev(tbp, actuel);

    tbp->contenu[ind]->precedent = prev;
}

void testamentTabPrev(tab_prev* tbp) {
    for (int i = 0; i < tbp->nb_items; i++) {
        tbp->contenu[i]->actuel = NULL;
        tbp->contenu[i]->precedent = NULL;
        free(tbp->contenu[i]);
    }
}

// ========================== DIJKSTRA ==================== //

void dijkstra_source(graphe* g, Noeud* source, bool verbose) {
    if (verbose) {
        cout << "Dans Dijkstra_source()" << endl;
    }

    Noeud* n_min;
    int dist;

    tab_prev * tbp = initTabPrev();
    tab_dist * tbd = initTabDist();

    if (verbose) {
        cout << "Init des tabPrev et tabDist ok" << endl;
    }

    file_prio * fp = initFilePrio();

    if (verbose) {
        cout << "Init de filePrio ok" << endl;
    }



    ajoutPriorite(fp, source, 0, verbose);
    if (verbose) {
        cout << endl << "Ajout de source dans filePriod ok" << endl;
    }
    ajoutElemDist(tbd, source, 0);

    if (verbose) {
        cout << "Avant les ajouts dans les listes" << endl;
    }

    for (int i = 0; i < g->nb_noeuds; i++) {

        if (strcmp(g->noeuds[i]->nom, source->nom) != 0) {
            if (verbose) {
                cout << endl << "----------------------------------------" << endl;
                cout << endl << " noeud en cours d'ajout : " << g->noeuds[i]->nom << endl;
            }
            ajoutElemDist(tbd, g->noeuds[i], -1);
            ajoutElemPrev(tbp, g->noeuds[i], NULL);
            ajoutPriorite(fp, g->noeuds[i], -1, verbose);
        }
    }

    // <editor-fold defaultstate="collapsed" desc="verbose">
    if (verbose) {
        cout << endl << " ------ Avant boucle de calcul --------" << endl;

        cout << endl << "Affichage de la file de priorite" << endl;
        for (int i = 0; i < fp->nb_items; i++) {
            cout << "Item de la file " << i << " : " << fp->file[i]->n->nom << " - prio : " << fp->file[i]->val << endl;
        }

        cout << endl << "Affichage du min de la file de prio" << endl;

        cout << "  " << fp->file[fp->ind_min]->n->nom << " - prio : " << fp->file[fp->ind_min]->val << endl;

        cout << endl << "Affichage de la liste de distance " << endl;
        for (int i = 0; i < tbd->nb_items; i++)
            cout << "  " << tbd->contenu[i]->destination->nom << " : " << tbd->contenu[i]->distance << endl;

        cout << endl << "Affichage de la liste de precedents " << endl;
        for (int i = 0; i < tbp->nb_items; i++)
            cout << "  " << tbp->contenu[i]->actuel->nom << " : " << (tbp->contenu[i]->precedent == NULL ? "NULL" : tbp->contenu[i]->precedent->nom) << endl;

        cout << endl << endl << "------- Boucle de calcul ------" << endl;

        cout << "Test file vide : " << (fileVide(fp) == false ? "File pas vide" : "File vide") << endl;
    }// </editor-fold>

    while (!fileVide(fp)) {
        if (verbose) {
            cout << endl << " *** dans la boucle ***" << endl << endl;
        }

        n_min = enleveMin(fp, verbose);

        if (verbose) {
            cout  << endl << "noeud en cours : " << n_min->nom << endl;
            cout << " nb_arc_ext : " << n_min->nb_arc_ext << endl;
        }

        for (int i = 0; i < n_min->nb_arc_ext; i++) {
            Noeud* v = n_min->arc_inc_ext[i]->dst;

            if (contientElem(fp, v)) {
                dist = 0;
                dist = (distanceNoeud(tbd, n_min) != -1 ? distanceNoeud(tbd, n_min) : 0) + n_min->arc_inc_ext[i]->valeur;

                if (verbose) {
                    cout << "Distance de " << v->nom << " a la source = " << dist << endl;
                }

                if (distanceNoeud(tbd, v) == -1 || distanceNoeud(tbd, v) > dist) {
                    setElemPrev(tbp, v, n_min);
                    modifDist(tbd, v, dist);
                    diminuePriorite(fp, v, dist);
                }
            }

            // <editor-fold defaultstate="collapsed" desc="verbose">
            if (verbose) {

                cout << endl << "Affichage de la file de priorite" << endl;
                for (int i = 0; i < fp->nb_items; i++) {
                    cout << "Item de la file " << i << " : " << fp->file[i]->n->nom << " - prio : " << fp->file[i]->val << endl;
                }

                cout << endl << "Affichage du min de la file de prio" << endl;

                if (!fileVide(fp))
                    cout << "  " << fp->file[fp->ind_min]->n->nom << " - prio : " << fp->file[fp->ind_min]->val << endl;

                cout << endl << "Affichage de la liste de distance " << endl;
                for (int i = 0; i < tbd->nb_items; i++)
                    cout << "  " << tbd->contenu[i]->destination->nom << " : " << tbd->contenu[i]->distance << endl;

                cout << endl << "Affichage de la liste de precedents " << endl;
                for (int i = 0; i < tbp->nb_items; i++)
                    cout << "  " << tbp->contenu[i]->actuel->nom << " : " << (tbp->contenu[i]->precedent == NULL ? "NULL" : tbp->contenu[i]->precedent->nom) << endl;
                cout << endl;
            }// </editor-fold>

        }

    }

    
    cout  << endl<< "Affichage des chemins les plus courts en partant de " << source->nom << endl;
    string chemin = "";
    string fleche = "->";
    string point = " : ";
    Noeud* tmp_prev;
    
    
    if(verbose) {
        cout << " nb_items de tab_prev : " << tbp->nb_items << endl;
    }
        
    for(int i = 0; i < tbp->nb_items; i++) {
        tmp_prev = tbp->contenu[i]->actuel;
        
        chemin = tmp_prev->nom;
        
        dist = distanceNoeud(tbd, tmp_prev);
        
        chemin = chemin + point + to_string(dist);
        
        tmp_prev = tbp->contenu[rechercheItemPrev(tbp, tmp_prev)]->precedent;
        
        while(strcmp(tmp_prev->nom, source->nom) != 0) {
            
            chemin = tmp_prev->nom + fleche + chemin;
            
            tmp_prev = tbp->contenu[rechercheItemPrev(tbp, tmp_prev)]->precedent;
            
        }
        
        chemin = source->nom + fleche + chemin;
        
        cout << chemin << endl;
    }
    
    


    testamentFile(fp);
    testamentTabDist(tbd);
    testamentTabPrev(tbp);

    if (verbose) {
        cout << "Sortie de dijkstra_source()" << endl;
    }

}
